#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>


void InsertSort(int arr1[], int n) {
	int i, j, tmp;
	for (i = 1; i < n; i++) {
		if (arr1[i] < arr1[i - 1]) {
			tmp = arr1[i];
			for (j = i - 1; j >= 0 && arr1[j] > tmp; j--)
				arr1[j + 1] = arr1[j];
			arr1[j + 1] = tmp;
		}
	}
}


void SentryInsertSort(int arr[], int n) {
	int i, j;
	for (i = 2; i <= n; i++) {
		if (arr[i] < arr[i - 1]) {
			arr[0] = arr[i];
			for (j = i - 1; arr[j] > arr[0]; j--) {
				arr[j + 1] = arr[j];
			}
			arr[j + 1] = arr[0];
		}
	}
}


void BinaryInsertSort(int arr[], int n) {
	int i, j, low, high, mid, tmp;
	for (i = 1; i < n; i++) {
		if (arr[i] < arr[i - 1]) {
			tmp = arr[i];
			low = 0;
			high = i - 1;
			while (low <= high) {
				mid = (low + high) / 2;
				if (arr[mid] > tmp) {
					high = mid - 1;
				}
				else {
					low = mid + 1;
				}
			}
			for (j = i - 1; j >= low; j--) {
				arr[j + 1] = arr[j];
			}
			arr[j + 1] = tmp;
		}
	}
}


int main() {
	int arr1[] = { 5, 3, 7, 8, 4, 10 };
	int sz = sizeof(arr1) / sizeof(arr1[0]);
	printf("%p\n", &arr1);
	InsertSort(arr1, sz);

	for (int i : arr1) {
		printf("%d, ", i);
	}

	printf("\n");
	int arr2[] = { 0, 5, 3, 7, 8, 4, 10 };
	int sz2 = sizeof(arr1) / sizeof(arr1[0]);
	SentryInsertSort(arr2, sz2-1);
	for (int j : arr2) {
		printf("%d, ", j);
	}

	printf("\n");
	int arr3[] = { 5, 3, 7, 8, 4, 10 };
	BinaryInsertSort(arr3, sz);
	for (int i : arr3) {
		printf("%d, ", i);
	}
	printf("\n");

	return 0;
}
